package BFS解决FloodFill算法.多源;

import java.util.LinkedList;
import java.util.Queue;

public class 飞地的数量 {

    int [] dx = {0,0,1,-1};
    int [] dy = {1,-1,0,0};
    public int numEnclaves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        Queue<int []> q = new LinkedList<>();
        boolean [][] visited = new boolean[m][n];
        // 1.进行边界为 1的预处理
        for(int i = 0;i<m;i++)
        {
            for(int j = 0;j<n;j++)
            {
                if( i ==0 || i== m-1 || j==0 || j== n-1)
                {
                    if(grid[i][j] == 1)
                    {
                        q.add(new int []{i,j});
                        visited[i][j] = true;
                    }
                }
            }
        }


    //2.从边界进行遍历，看是否能遍历到1
        while (!q.isEmpty())
        {

            int [] cur = q.poll();
            int a = cur[0],b =  cur[1];
            for(int i = 0;i<4;i++)
            {
                int x = a+dx[i];
                int y = b+dy[i];
                if(x>=0 && x<m && y>=0&& y<n && grid[x][y] == 1 &&!visited[x][y])
                {

                   visited[x][y]  = true;
                   q.add(new int []{x,y});

                }
            }
        }

        // 3.把边界遍历不到的1进行统计
        int count = 0;
        for(int i = 0 ;i<m;i++)
        {
            for(int j = 0 ;j<n;j++)
            {
                if(!visited[i][j] && grid[i][j] == 1)
                {
                    count++;
                }
            }
        }
        return count;
    }

}
